import sun.reflect.generics.tree.Tree;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:验证有效二叉树、二叉搜索树与双向链表、路径总和
 * Date: 2024-02-09
 * Time:10:48
 */
public class Solution {
      static class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;

          TreeNode() {
          }

          TreeNode(int val) {
              this.val = val;
          }

          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }

      //思路一：栈

/*      Stack<TreeNode> stack = new Stack<>();
        public boolean isValidBST(TreeNode root) {
          //中序遍历，节点入栈
          inorderTravel(root);
          TreeNode peek2 = null;
          while(!stack.isEmpty()) {
              TreeNode peek1 = stack.pop();
              if(!stack.isEmpty())
                  peek2 = stack.peek();
              else {
                  return true;
              }
              //TreeNode pop = stack.pop();
              if(peek1.val <= peek2.val) {
                  return false;
              }
          }
          return true;

      }

    private void inorderTravel(TreeNode root) {
        if(root == null)
            return;
        inorderTravel(root.left);
        stack.push(root);
        inorderTravel(root.right);
    }
*/

    //思路二：顺序表
    List<TreeNode> list = new ArrayList<>();
    private void inorderTravel(TreeNode root) {
        if(root == null)
            return;
        inorderTravel(root.left);
        list.add(root);
        inorderTravel(root.right);
    }

    public boolean isValidBST(TreeNode root) {
        inorderTravel(root);
        for(int i = 0;i < list.size()-1;i++) {
            int val1 = list.get(i).val;
            int val2 = list.get(i+1).val;
            if(val1 >= val2)
                return false;
        }
        return true;
    }
///////////////////////////////////////////////////////////
    //二叉树所有路径
    public List<String> binaryTreePaths(TreeNode root) {
        List<TreeNode> path = new ArrayList<>();
        List<String> result = new ArrayList<>();
        dfs(root,path,result);
        return result;
    }

    private void dfs(TreeNode root,List<TreeNode> path,List<String> result) {
        path.add(root);
        if(root.left == null && root.right == null) {  //到叶子节点说明该路径已经遍历完了，接下来就是把路径放到结果集里面
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i < path.size();i++) {
                int tmp = path.get(i).val;
                sb.append(tmp);
                if(i != path.size()-1)
                    sb.append("->");  //除了最后一个元素，其他的每次要在后面加上"->"
            }
            result.add(sb.toString());
            return;
        }

        if(root.left != null) {
            dfs(root.left, path, result);
            path.remove(path.size()-1);  //左子树遍历完之后弹出，去遍历另一边（回溯算法）
        }
        if(root.right != null) {
            dfs(root.right, path, result);
            path.remove(path.size()-1);
        }
    }


////////////////////////////////////////////////////////////
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return false;
    }

//////////////////////////////////////////////////////////////
    //二叉搜索树最小绝对差
    public int getMinimumDifference(TreeNode root) {
        inorderTravel(root);
        int minSub = 10001;
        for(int i = 0;i < list.size()-1;i++) {
            int val1 = list.get(i).val;
            int val2 = list.get(i+1).val;
            if(val2-val1 < minSub)
                minSub = val2 - val1;
        }
        return minSub;
    }

}
